/**
 * 对常见哈希算法的实现。
 */
#ifndef _AHAMOLETT_CLANG_DATASTRUCT_HASH_H_
#define _AHAMOLETT_CLANG_DATASTRUCT_HASH_H_

#include <stddef.h>

/* bkdr 哈希算法进行计算时使用的魔法数。 */
#define BKDR_HASH_MAGIC_NUM 131

/**
 * @brief 字符串哈希算法 BKDR Hash。
 * 
 * 输入字符串，输出 unsigned long 大小的哈希值。
 * 
 * @param str 计算哈希值的字符串。
 * @param n 为 0 时计算整个字符串的哈希值，为 1 时最多计算前 n 个字符组成字符串的哈希值。
 * 
 * @return unsigned long 字符串的哈希值。
 */
static inline unsigned long bkdr_hash_func(const char *str, size_t n)
{
    unsigned long ret = 0;
    unsigned char *_str = (unsigned char *)str;
    unsigned char *_str_stop = (unsigned char *)str + n;
    do {
        ret += *_str * BKDR_HASH_MAGIC_NUM;
        ret += *_str;
        _str++;
    } while (*str != '\0' && _str != _str_stop);

    return ret;
}

/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL
/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL

/**
 * @brief Linux 的 64 位哈希算法。
 * 
 * @param val 进行计算的无符号长整数。
 * @param bits 期望计算结果保留的最大位数。
 * 
 * @return unsigned long 计算得到的哈希值。
 */
static inline unsigned long hash_64(unsigned long val, unsigned int bits)
{
    unsigned long hash = val * GOLDEN_RATIO_PRIME_64;
    return hash >> (64 - bits);
}

/**
 * @brief Linux 的 32 位哈希算法。
 * 
 * @param val 进行计算的无符号整数。
 * @param bits 期望计算结果保留的最大位数。
 * 
 * @return unsigned int 计算得到的哈希值。
 */
static inline unsigned int hash_32(unsigned int val, unsigned int bits)
{
    unsigned int hash = val * GOLDEN_RATIO_PRIME_32;
    return hash >> (32 - bits);
}

#endif
